package com.hard;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by Lxk on 2019/7/7.
 */
public class Solution239 {

    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums==null||k==0){
            int[] res = new int[0];
            return res;
        }
        int[] res = new int[nums.length-k+1];
        Deque<Integer> deque = new LinkedList<>();
        int pos = 0;
        for(int i = 0;i < nums.length; i++){
            while(!deque.isEmpty()&&nums[deque.getLast()]<=nums[i]){
                deque.pollLast();
            }
            deque.addLast(i);
            if(deque.getFirst()==i-k){
                deque.pollFirst();
            }
            if(i>=k-1){
                res[pos++] = nums[deque.peekFirst()];
            }
        }
        return res;
    }

}
